/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-07 15:24:06
 * @LastEditors: lily
 * @LastEditTime: 2021-04-07 16:17:43
 */
/*
 * @lc app=leetcode.cn id=239 lang=javascript
 *
 * [239] 滑动窗口最大值
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */

// 思路：单调队列

// 复杂度：O(n) O(n)

var maxSlidingWindow = function (nums, k) {
    // deque存放下标
    let len = nums.length, deque = [], res = []
    for (let i = 0; i < len; i++) {
        // 在滑动窗口之外的直接从队头删掉
        // 当前下标比存储的先的下标大
        if (i - deque[0] >= k) {
            deque.shift()
        }
        // 如果新加进来的数比单调队列中原来的数都要大，则直接弹出队列中的其他数
        while (nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop()
        }
        deque.push(i)
        // 从数组第k个元素开始存
        if (i > k - 2) {
            res.push(nums[deque[0]])
        }
    }
    return res

};
// @lc code=end

console.log(maxSlidingWindow([1, 3, 1, 2, 0, 5], 3))